package Elementary_algorithm.DynamicProgramming;

import org.junit.Test;

/*
爬楼梯
假设你正在爬楼梯。需要 n阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

作者：LeetCode
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn854d/
 */
public class _01爬楼梯 {

    @Test
    public void test() {
        System.out.println(climbStairs1(45));
    }

    //超时
    public int climbStairs(int n) {
        return dfs(n);
    }

    public int dfs(int n) {
        int method;
        if(n == 1)
            return 1;
        if(n == 2)
            return 2;
        method = dfs(n-1) + dfs(n-2);
        return method;
    }

    //官解：方法一：动态规划
    //根据题意可得每个台阶的公式 f(x)=f(x−1)+f(x−2)
    public int climbStairs1(int n) {
        int p = 0,q = 0,r = 1;
        //从 q=r 不难看出 p 是 f(x−2)  q 是 f(x−1)
        //同时这里采用了滚动数组的思想将空间复杂度变成了O(1)
        for (int i = 0; i < n; i++) {
            //通过对象传递参数,并将答案的对象r(即f(x))设置为1,其余为0,可以通过for循环而不是递归构建出 f(x)=f(x−1)+f(x−2)+...
            p = q; //f(x−2)
            q = r; //f(x−1)
            r = q + p;
        }
        return r;
    }
}
